Traditional computer architectures were based on a sequential model of program execution wherein instructions issued and executed sequentially. That is, each instruction finished before the next instruction started. Error recovery pursuant to this model is very easy because the process state (e.g., the program counter, the general purpose registers, and main memory) which exists when an interrupt condition is detected is predetermined and consistent with the last instruction to successfully execute. Consequently, the process may be restarted by executing the program instruction which directly follows the last instruction to successfully execute.
As technology advanced, pipelined processors were constructed wherein several instructions could be in some phase of execution at the same time. Unfortunately, pipelined instructions may modify the process state in an order different from that defined by the sequential architectural model. Thus, when an interrupt condition is detected, the process state usually does not correspond to the state that would exist if all instructions executed sequentially. That makes restarting the process very difficult, if not impossible.
Techniques for implementing interrupts in pipelined processors are disclosed in "Implementing Precise Interrupts In Pipelined Processors," by James E. Smith, et al., IEEE Transactions on Computers, Volume 37, No. 5, May, 1988, pages 562-573, incorporated herein by reference. In one method disclosed therein (the result shift register method), an instruction can modify the process state only when all previously issued instructions are known to be free of exception conditions. To accomplish this, an N-stage result shift register is used to control instruction execution, where N represents the maximum number of clock periods that an instruction may require to complete. An instruction that takes i clock periods to execute places control information in stage i of the result shift register at the time it issues. During each clock period, the control information is shifted down one stage towards stage one. When the control information reaches stage one, it is used during the next clock period to control the hardware so that the result data generated by the instruction is stored at that time in the correct result register.
To insure that the instructions modify the process state in order, the control information for an instruction must not be placed in stage i of the result shift register when the control information for a previously issued instruction is in stage j (j being greater than i). Thus, an issuing instruction that places control information in stage j reserves all lesser numbered stages. A subsequent instruction which designates a reserved stage must wait at the issue stage until the designated stage is no longer reserved.
The primary disadvantage of this method is that fast instructions may sometimes get held up at the issue register even if they are independent of the other instructions and could otherwise issue. In addition, the held instructions block the issue register when slower instructions behind them could presumably issue.
Another disclosed method (the reorder buffer method) overcomes the foregoing disadvantages by allowing instructions to finish out of order, but a special circular buffer, termed a reorder buffer, is used in addition to a result shift register to reorder the instructions before they modify the process state. Every time an instruction issues, control information is loaded in the next sequential reorder buffer stage which includes a space reserved for the result data generated by the instruction. The reorder buffer entries thus preserve the issue sequence. A tag is placed in the appropriate result shift register stage to identify the reorder buffer entry corresponding to the instruction.
When an instruction completes, both the result data and any exception conditions are stored in the reorder buffer. When the entry at the head of the reorder buffer contains valid results (its corresponding instruction has completed), then the exception data is checked. If no exception conditions are detected, the result data is written into the registers. If an exception is detected, instruction issuing stops, and all further writes into the register file are inhibited.
While this method is an improvement over the result shift register method, it still suffers a performance penalty. For example, a computed result that is generated out of order is held in the reorder buffer until previous instructions, finishing later, have updated the register file, even if the instructions are independent. Furthermore, an instruction dependent on a result being held in the reorder buffer cannot issue until the result has been written into the register file.
A third disclosed method (the history buffer method) attempts to overcome the disadvantages of both the result shift register method and the reorder buffer method. With this method, computed results are placed in a working register file, but enough state information is stored in a history buffer so that a precise state can be restored if an exception occurs. The history buffer is organized and functions in a manner very similar to the reorder buffer. When an instruction issues, a history buffer entry is loaded with control information, and the current value of the destination register (to be overwritten by the issuing instruction) is also read from the register file and written into the buffer entry. The result data generated by the instruction are written directly into the register file when an instruction completes. Exception data are written into the history buffer. When the history buffer contains an entry at the head that is known to have finished without exceptions, the history buffer entry is no longer needed and that buffer location can be reused.
When an exception condition is detected at the head entry of the buffer, the buffer is held, instruction issue is immediately halted, and the instructions in the pipeline are canceled. The active buffer entries are then emptied from tail to head, and the history values are loaded back into their corresponding registers. The program then may be restarted by reissuing the instruction which caused the exception condition and all subsequent instructions. A major disadvantage of this scheme is the cancellation of the instructions in the pipeline register at the time the exception condition is detected. The canceled instructions must be re-executed when the system restarts even though they could have successfully completed at the time the exception condition was detected.